HDU 5109 Alexandra and AB Problem

HDU_5109

描述

给一个整数N和数字串S，找一个最小的整数M，M中包括S，并且M是N的倍数。

思路

BestCoder官方题解：

最后的A*B应该是xSy的形式，其中y可以为空，并且如果S不以0开头那么x也可以为空。
首先枚举y的长度。在y的长度确定之后，显然x应该越小越好。所以从小到大枚举x。设S的长度为p，y的长度为q，那么可以列方程：((x∗10p+S)∗10q+y)modA=0。解出y以后，如果y<10q那么解合法。
容易证明，我们只需从0（或1，如果S以0开头）到A枚举x，那么所有的解一定会被枚举到。对于q=0的情况，x的长度不会超过4，所以y的长度也只需要枚举到4就可以了。
对于所有枚举出的长度算出的答案取最优解即可。

c++代码

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdlib>
#include <cstdio>
using namespace std;
#define ll long long
ll A,dig[20];
char s[10];
ll work(){
    ll len=strlen(s),i,ans,tail,tmp,ss,mins=1e18;
    ss=atoll(s);
    if( s[0]=='0' && len==1)return 0;
    for(i=(s[0]=='0') ; i<=A ; i++ ){
        for(int j=0 ; j<=4;j++){
            tmp=i*dig[len+j]+ss*dig[j];
            tail=(A-tmp%A)%A;
            if(tail<dig[j])
                mins=min(tmp+tail,mins);
        }
    }
    return mins/A;
}
int main(){
    dig[1]=10;dig[0]=1;
    for(int i=2;i<20;i++)dig[i]=dig[i-1]*10;
    while(scanf("%d%s",&A,s)!=EOF){
        printf("%I64d\n",work());
    }
    return 0;
}